/*
 * The RavenX Library
 * Copyright (c) 2008 by Solidus
 * 
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.It is provided "as is" without express 
 * or implied warranty.
 *
 */

#include "rx_vector.h"
#include "rx_misc.h"
#include "rx_debug.h"
#include "rx_mem.h"
#include "rx_algo.h"

RX_SPACE_BEG


typedef struct __rx_vector_tag
{
		rx_byte					*start;
		rx_byte					*finish;
		rx_byte					*end_of_storage;
		
		rx_info_t				info;
		rx_alloc_t				alloc;
}rx_vector_t;


static RX_INLINE rx_bool __vector_is_valid(const rx_vector_t *self)
{
		if(self == NULL || self->info.elem_size == 0 || self->info.init_f == NULL || self->info.copy_f == NULL || self->info.uninit_f == NULL) return rx_false;
		if(self->alloc.alloc_f == NULL || self->alloc.dealloc_f == NULL || self->alloc.realloc_f == NULL) return rx_false;
		if(self->start > self->finish || self->start > self->end_of_storage || self->finish > self->end_of_storage) return rx_false;

		return rx_true;
}

static RX_INLINE void __vec_init(void *start, size_t n, size_t elem_size, void (*init_f)(void *ptr, size_t esize))
{
		size_t i = 0;
		while(i < n){ init_f(RX_GET_ELEM(start, elem_size, i), elem_size); i++;}
}

static RX_INLINE void __vec_uninit(void *start, size_t n, size_t elem_size, void (*uninit_f)(void *ptr, size_t esize))
{
		size_t i = 0;
		while(i < n){ uninit_f(RX_GET_ELEM(start, elem_size, i), elem_size); i++;}
}


const rx_info_t* rx_vector_info(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return &self->info;
		
}
const rx_alloc_t* rx_vector_allocator(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return &self->alloc;
}


rx_vector_t* rx_vector_create(const rx_info_t *info, const rx_alloc_t *palloc)
{
		rx_vector_t* self;
		
		if(palloc == NULL)palloc = rx_mem_default_alloctor();
		RX_ASSERT(palloc != NULL && palloc->alloc_f != NULL && palloc->dealloc_f != NULL &&palloc->realloc_f != NULL);

		self = (rx_vector_t*)palloc->alloc_f(sizeof(rx_vector_t), palloc->ctx);
		self->alloc = *palloc;
		RX_ASSERT(info != NULL);

		self->start = self->finish = self->end_of_storage = NULL;
		self->info = *info;
		rx_install_info(&self->info);
		
		RX_ASSERT(__vector_is_valid(self));

		return self;
}

void rx_vector_reserve(rx_vector_t *self, size_t size)
{
		size_t cap_size, old_size;
		rx_byte *new_start;
		RX_ASSERT(__vector_is_valid(self));
		
		cap_size = rx_vector_capacity(self);
		old_size = rx_vector_size(self);
		
		if(cap_size >= size)return;

		new_start = (rx_byte*)self->alloc.alloc_f(size * self->info.elem_size, self->alloc.ctx);

		RX_FATAL_ERROR(new_start != NULL);
				
		if(cap_size > 0)
		{
				if(old_size > 0)
				{
						__vec_init(new_start, old_size, self->info.elem_size, self->info.init_f);
						rx_copy(self->start, self->finish, new_start, self->info.elem_size, self->info.copy_f);
						__vec_uninit(self->start, old_size, self->info.elem_size,self->info.uninit_f);
				}
				self->alloc.dealloc_f(self->start,   self->alloc.ctx);
		}
		self->start = new_start;
		self->finish = new_start + old_size * self->info.elem_size;
		self->end_of_storage = new_start + size * self->info.elem_size;

}

void rx_vector_resize(rx_vector_t *self, size_t size)
{
		size_t old_size;
		RX_ASSERT(__vector_is_valid(self));
		
		old_size = rx_vector_size(self);
		
		if(old_size == size)return;

		rx_vector_reserve(self, size);
		
		if(size < old_size)
		{
				rx_vector_erase_range(self, rx_vector_at(self, size), rx_vector_end(self));
		}else
		{
				__vec_init(self->start + (self->info.elem_size * old_size), size -old_size, self->info.elem_size, self->info.init_f);
				self->finish = self->start + self->info.elem_size * size;
		}
}


rx_vector_t* rx_vector_copy(const rx_vector_t *self)
{
		rx_vector_t* res;
		RX_ASSERT(__vector_is_valid(self));
		res = rx_vector_create(&self->info, &self->alloc);
		if(rx_vector_size(self) > 0)
		{
				rx_vector_resize(res, rx_vector_size(self));

				rx_copy(rx_vector_begin((rx_vector_t*)self), rx_vector_end((rx_vector_t*)self), rx_vector_begin(res), self->info.elem_size, self->info.copy_f);
		}
		return res;
}

void rx_vector_clear(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		
		rx_vector_resize(self, 0);
}


void rx_vector_destroy(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));

		rx_vector_clear(self);
		self->alloc.dealloc_f(self->start,   self->alloc.ctx);
		self->alloc.dealloc_f(self,   self->alloc.ctx);


}

size_t rx_vector_size(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return (self->finish - self->start) / self->info.elem_size;
}


size_t rx_vector_capacity(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return (self->end_of_storage - self->start) / self->info.elem_size;
}



void* rx_vector_insert(rx_vector_t *self, void *pos, const void *value)
{

		RX_ASSERT(__vector_is_valid(self));
		

		if(self->finish < self->end_of_storage)
		{
				RX_ASSERT((rx_byte*)pos >= self->start && (rx_byte*)pos <= self->finish);

				self->info.init_f(self->finish, self->info.elem_size);
				self->finish += self->info.elem_size;
				rx_copy_backward(pos, self->finish - self->info.elem_size, self->finish, self->info.elem_size, self->info.copy_f);
				self->info.copy_f(pos, value, self->info.elem_size);
				return pos;
		}else
		{
				rx_byte *new_start, *new_finish, *tmp;
				
				const size_t old_size = rx_vector_size(self);
				const size_t new_size = old_size != 0 ? old_size * 2 : 1;

				new_start = (rx_byte*)self->alloc.alloc_f(self->info.elem_size * new_size, self->alloc.ctx);

				RX_FATAL_ERROR(new_start != NULL);
				new_finish = new_start + self->info.elem_size * (rx_vector_size(self) + 1);

				__vec_init(new_start, old_size + 1, self->info.elem_size,self->info.init_f);
				tmp = (rx_byte*)rx_copy(self->start, pos, new_start, self->info.elem_size, self->info.copy_f);
				self->info.copy_f(tmp, value, self->info.elem_size);
				tmp += self->info.elem_size;
				
				if(tmp < new_finish) rx_copy(pos, self->finish, tmp, self->info.elem_size, self->info.copy_f);
				
				__vec_uninit(self->start, old_size, self->info.elem_size, self->info.uninit_f);
				self->alloc.dealloc_f(self->start,   self->alloc.ctx);


				self->start = new_start;
				self->finish = new_finish;
				self->end_of_storage = new_start + new_size * self->info.elem_size;
				return (void*)(tmp - self->info.elem_size);
		}
}

void* rx_vector_insert_pos(rx_vector_t *self, size_t pos, const void *value)
{
		void* ptr;
		
		RX_ASSERT(__vector_is_valid(self));
		
		ptr = rx_vector_at(self, pos);

		return rx_vector_insert(self, ptr, value);
}

void* rx_vector_insert_range(rx_vector_t *self,  void *pos,  const rx_vector_t *other, const void *first,  const void *last)
{
		void *pf;
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(__vector_is_valid(other));

		pf = NULL;

		while(first != last)
		{
				pos = rx_vector_insert(self, pos, (void*)first);
				if(pf == NULL)pf = pos;
				pos = rx_vector_next(self, pos);
				first = rx_vector_next((rx_vector_t*)other, (void*)first);
		}
		return pf;
}

void rx_vector_push_back_range(rx_vector_t *self, const rx_vector_t *other, const void *first, const void *last)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(__vector_is_valid(other));
		rx_vector_insert_range(self, self->finish, other, first, last);
}

rx_bool rx_vector_is_empty(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return (self->finish - self->start) == 0 ? rx_true : rx_false;
}


void*   rx_vector_at(rx_vector_t *self, size_t idx)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(idx < rx_vector_size(self));
		return RX_GET_ELEM(self->start, self->info.elem_size, idx);
}



void*  rx_vector_begin(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return self->start;
}


void*  rx_vector_end(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return self->finish;
}


void* rx_vector_next(rx_vector_t *self, void *curr)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT((rx_byte*)curr < self->finish && (rx_byte*)curr >= self->start);
		return ((rx_byte*)curr + self->info.elem_size);
}

void* rx_vector_front(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));

		if(rx_vector_is_empty(self)) return NULL;
		return self->start;
}

void* rx_vector_back(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		if(rx_vector_is_empty(self)) return NULL;
		
		return rx_vector_at(self, rx_vector_size(self) - 1);
}



void rx_vector_push_back(rx_vector_t *self, const void *value)
{
		RX_ASSERT(__vector_is_valid(self));
		
		if(rx_vector_size(self) < rx_vector_capacity(self))
		{
				self->info.init_f(self->finish, self->info.elem_size);
				self->info.copy_f(self->finish, value, self->info.elem_size);
				self->finish += self->info.elem_size;
		}else
		{
				rx_vector_insert(self, self->finish, value);
		}
}



void rx_vector_push_front(rx_vector_t *self, const void *value)
{
		RX_ASSERT(__vector_is_valid(self));
		rx_vector_insert(self, self->start, value);
}

void rx_vector_pop_front(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(!rx_vector_is_empty(self));
		
		rx_vector_erase(self, self->start);
}

void rx_vector_pop_back(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(!rx_vector_is_empty(self));

		self->finish -= self->info.elem_size;
		self->info.uninit_f(self->finish, self->info.elem_size);
}


void* rx_vector_erase(rx_vector_t *self, void *pos)
{
		rx_byte *p = (rx_byte*)pos;
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(!rx_vector_is_empty(self));
		RX_ASSERT(p >= self->start && p < self->finish);

		if((p + self->info.elem_size) != self->finish)
		{
				rx_copy((const void*)(p + self->info.elem_size), self->finish, (void*)p, self->info.elem_size, self->info.copy_f);
		}

		self->finish -= self->info.elem_size;

		self->info.uninit_f(self->finish, self->info.elem_size);
		return (void*)p;
}

void* rx_vector_erase_index(rx_vector_t *self, size_t beg, size_t count)
{
		void *first, *last;
		size_t n;
		RX_ASSERT(__vector_is_valid(self));
		n = rx_vector_size(self);
		RX_ASSERT(beg < n);

		first = rx_vector_at(self, beg);
		last = ((beg + count) < n ?  rx_vector_at(self, beg + count) : rx_vector_end(self));

		return rx_vector_erase_range(self, first, last);
}

void* rx_vector_erase_range(rx_vector_t *self, void *first, void *last)
{
		rx_byte *b = (rx_byte*)first;
		rx_byte *e = (rx_byte*)last;

		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(!rx_vector_is_empty(self));
		RX_ASSERT(b >= self->start && b < self->finish);
		RX_ASSERT(e <= self->finish && e > b);

		if(e != self->finish)
		{
				b = (rx_byte*)rx_copy(e, self->finish, b, self->info.elem_size, self->info.copy_f);
				e = self->finish;
		}
		self->finish = b;

		while(b != e)
		{
				self->info.uninit_f((void*)b, self->info.elem_size);
				b += self->info.elem_size;
		}

		return first;
}


size_t rx_vector_element_size(const rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		return self->info.elem_size;
		
}



rx_int_n rx_vector_indexof(rx_vector_t *self, const void *key)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(self->info.cmp_f != NULL);
		RX_ASSERT(key != NULL);
		if(rx_vector_size(self) == 0)return -1;
		return rx_find(key, rx_vector_at(self,0), rx_vector_size(self), self->info.elem_size, self->info.cmp_f);

}



void rx_vector_sort(rx_vector_t *self)
{
		RX_ASSERT(__vector_is_valid(self));
		RX_ASSERT(self->info.swap_f != NULL && self->info.cmp_f != NULL);
		
		if(rx_vector_size(self) > 2)
		{
				rx_quick_sort(rx_vector_begin(self), rx_vector_size(self), rx_vector_element_size(self), self->info.cmp_f, self->info.swap_f);
		}
}

rx_bool rx_vector_add_distinct(rx_vector_t *self, const void *key)
{
		rx_int_n i = rx_vector_indexof(self, key);

		if(i == -1)
		{
				rx_vector_push_back(self, key);
				return rx_true;
		}else
		{
				return rx_false;
		}
}



void	rx_vector_swap(rx_vector_t *l, rx_vector_t *r)
{
		rx_vector_t tmp;
		RX_ASSERT(__vector_is_valid(l));
		RX_ASSERT(__vector_is_valid(r));
		tmp = *l; *l = *r; *r = tmp;

}

RX_SPACE_END





#if(0)

#if(0)
void rx_vector_resize(rx_vector_t *self, size_t size)
{
		size_t cap_size, old_size;
		RX_ASSERT(__vector_is_valid(self));
		
		cap_size = rx_vector_capacity(self);
		old_size = rx_vector_size(self);
		
		if(old_size == size)return;

		if(size > cap_size)
		{
				rx_byte *new_start = self->alloc.alloc_f(size * self->elem_size, self->alloc.ctx);
				
				if(new_start == NULL)rx_fatal("rx_vector_resize failed : memory allocation failed\n");
				
				__vec_init(new_start, old_size, self->elem_size, self->init_f);
				rx_copy(self->start, self->finish, new_start, self->elem_size, self->copy_f);
				__vec_uninit(self->start, old_size, self->elem_size,self->uninit_f);
				self->alloc.dealloc_f(self->start,  cap_size * self->elem_size, self->alloc.ctx);

				self->start = new_start;
				self->finish = new_start + old_size * self->elem_size;
				self->end_of_storage = new_start + size * self->elem_size;
		}
		
		if(size < old_size)
		{
				rx_vector_erase_range(self, rx_vector_at(self, size), rx_vector_end(self));
		}else
		{
				__vec_init(self->start + old_size, size -old_size, self->elem_size, self->init_f);
				self->finish = self->start + self->elem_size * size;
		}
}
#endif

#endif






